The present invention deals with cache line relocation among multiple caches in systems with coherent cache memories. Related art includes mechanisms for data forwarding in shared-memory multiprocessors as described in “Data Forwarding in Scalable Shared Memory Multiprocessors”, Koufaty et al, IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 12, December 1996, pages 1250-1264. In this approach, usage patterns based on traces or compile-time analysis are used to determine cases where one data item, when used by one processor, should be forwarded to the caches of other processors identified as consumers of the data item. This approach is limited in that (1) producer/consumer relationships must be identified using offline analysis of traces or compile-time analysis; (2) data items are forwarded using only identified producer/consumer relationships; and (3) data items are forwarded without regard to cost, for example without consideration as to whether the forwarded data item replaces more “useful” (in terms of improving system performance) data.
Among other related efforts is U.S. Pat. No. 6,711,651, Moreno et al, assigned to IBM, issued Mar. 23, 2004, “Method and Apparatus for History-Based Movement of Shared-Data in Coherent Cache Memories of a Multiprocessor System using Push Prefetching”. In this approach, a consume-after-produce table, implemented in hardware as part of the cache controller, is used to identify producer/consumer relationships for cache lines among multiple caches in a coherent cache memory system. A limitation of this approach is that cache lines are prefetched without regard to cost, for example (as previously described) without consideration as to whether the cache line replaces a more “useful” (in terms of improving system performance) cache line.
It would therefore be advantageous to relocate cache lines among multiple caches in a coherent cache memory system using cost-based mechanisms, that is, in such a fashion that overall system performance is always expected to be improved. One issue in evaluating the cost of relocating a cache line, which in general will replace another cache line, is the probability of re-reference for the two respective cache lines. As is well-known, this is highly correlated with cache line age, with more recently accessed cache lines being far more likely to be re-referenced than less recently accessed cache lines.
In view of the foregoing, a need has been recognized in connection with overcoming the shortcomings and disadvantages presented by conventional arrangements.